package org.chengn.level_middle.context2397;

import java.util.ArrayList;
import java.util.List;

/**
 * @Title: Context2397
 * @Author ChengN
 * @Package org.chengn.level_middle.context2397
 * @Date 2024/1/4 0:55
 * @description: 被列覆盖最多行数
 */
public class Context2397 {
    public int maximumRows(int[][] matrix, int numSelect) {
        if (numSelect == matrix[0].length) return matrix.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 1 << matrix[0].length; ++i) {
            if (isRight(i, matrix[0].length - numSelect)) list.add(i);
        }

        int[] matrixVal = new int[matrix.length];
        for (int i = 0; i < matrix.length; ++i) {
            matrixVal[i] = toBri(matrix[i]);
        }

        int res = 0;

        for (Integer shortVal : list) {
            int thisRes = 0;
            for (int i = 0; i < matrix.length; ++i) {
                if ((matrixVal[i] & shortVal) == 0) {
                    thisRes++;
                }
            }

            res = Math.max(res, thisRes);

        }

        return res;

    }

    private int toBri(int[] matrix) {
        int res = 0;
        for (int i = 0; i < matrix.length; ++i) {
            res += (matrix[i] << i);
        }
        return res;
    }

    private boolean isRight(int val, int num) {
        int res = 0;
        for (int i = 0; i < 13; ++i) {
            if ((val & 1 << i) > 0) res++;
        }
        return res == num;
    }
}
